import java.util.Arrays;

public class Solution300 {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] increase = new int[n];
        int index = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(increase, 0, index, num);
            if (i < 0) {
                increase[-i - 1] = num;
                if (-i - 1 == index) {
                    index++;
                }
            }
        }
        return index;
    }
}
